package com.demo;

public class Demo4 {
    public static void main(String[] args) {
        System.out.println(getMaxString("babad"));
        System.out.println(getMaxString("cbbd"));
        System.out.println(getMaxString("a"));
        System.out.println(getMaxString("ac"));
        System.out.println(getMaxString("abcdcba"));
    }

    public static String getMaxString(String str) {
        int len = str.length();
        if (len < 1) {
            return "";
        }
        int start = 0;
        int end = 0;
        // 找中心点，中心点可能是任意一个位置的一个字符或者两个字符
        for (int i = 0; i < len; i++) {
            int len1 = getSameStringLength(str, i, i);// 符文中心是一个字符
            int len2 = getSameStringLength(str, i, i + 1);// 符文中心是两个字符
            int maxLen = Math.max(len1, len2); // 取最大长度
            if(maxLen > end - start){ // 如果发现了新的回文，则更新起始位置和结束位置
                start = i - (maxLen - 1) / 2;// 用中心点位置减去回文长度的一半，得到回文起始位置
                end = i + maxLen / 2; // 用中心点位置加上回文长度的一半，得到回文结束位置
            }
        }
        return str.substring(start, end + 1);
    }

    public static int getSameStringLength(String str, int left, int right) {
        while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
            left--; // 左移
            right++; // 右移
        }
        // 返回回文长度
        return right - left - 1;
    }
}
